<!DOCTYPE html>
<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-0 vector-toc-not-available vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-0 skin-theme-clientpref-day vector-sticky-header-enabled" lang="de" dir="ltr"><head>
<meta charset="UTF-8">
<title>BQP</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="icon" type="image/png" href="./_res_/favicon.png">
<link rel="canonical" href="https://de.wikipedia.org/wiki/BQP"> <link href="./_mw_/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.wikimediamessages.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link href="./_mw_/ext.gadget.citeRef.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.defaultPlainlinks.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonHide.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonLayout.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonStyle.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiDarkmode.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiResponsive.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.specialSearch.css" rel="stylesheet" type="text/css">
<link rel="stylesheet" type="text/css" href="./_mw_/site.styles.css">
<link rel="stylesheet" type="text/css" href="./_mw_/noscript.css">
<link rel="stylesheet" type="text/css" href="./_res_/footer.css">
<link rel="stylesheet" type="text/css" href="./_res_/vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-BQP rootpage-BQP skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">BQP</span></h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="contentSub">
<div id="mw-content-subtitle"></div>
</div>
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">
<p>Die <a href="Komplexit%C3%A4tsklasse" title="Komplexitätsklasse">Komplexitätsklasse</a> <b>BQP</b> (von <span style="font-style:normal;font-weight:normal"><a href="Englische_Sprache" title="Englische Sprache">englisch</a></span> <span lang="en-Latn" style="font-style:italic"><i>bounded-error quantum polynomial time</i></span>) ist ein Begriff aus der <a href="Komplexit%C3%A4tstheorie" title="Komplexitätstheorie">Komplexitätstheorie</a>, einem Teilgebiet der <a href="Theoretische_Informatik" title="Theoretische Informatik">Theoretischen Informatik</a>. Zu BQP gehören alle Probleme, die auf einem <a href="Quantencomputer" title="Quantencomputer">Quantencomputer</a> in <a href="Polynomialzeit" title="Polynomialzeit">Polynomialzeit</a> mit einer Fehlerwahrscheinlichkeit von höchstens 1/3 lösbar sind. Sie ist das Äquivalent zur Klasse <a href="BPP_(Komplexit%C3%A4tsklasse)" title="BPP (Komplexitätsklasse)">BPP</a>, die für den <a href="Zeitkomplexit%C3%A4t" title="Zeitkomplexität">Zeitaufwand</a> auf <a href="Turingmaschine" title="Turingmaschine">Turingmaschinen</a> definiert ist. Wie bei der Klasse BPP ist auch bei BQP die Festlegung der Fehlerwahrscheinlichkeit auf 1/3 willkürlich, durch mehrmaliges Anwenden eines BQP-<a href="Algorithmus" title="Algorithmus">Algorithmus</a> kann eine beliebig niedrige Fehlerwahrscheinlichkeit erreicht werden.
</p><p>BQP wurde 1993 durch <a href="Umesh_Vazirani" title="Umesh Vazirani">Umesh Vazirani</a> und Ethan Bernstein eingeführt.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>
</p>
<div class="mw-heading mw-heading2"><h2 id="Beziehung_zu_anderen_Komplexitätsklassen"><span id="Beziehung_zu_anderen_Komplexit.C3.A4tsklassen"></span>Beziehung zu anderen Komplexitätsklassen</h2></div>
<p>Die Komplexitätsklassen <a href="P_(Komplexit%C3%A4tsklasse)" title="P (Komplexitätsklasse)">P</a> und BPP sind in BQP enthalten, BQP ist in <a href="Probabilistische_Polynomialzeit" title="Probabilistische Polynomialzeit">PP</a><sup id="cite_ref-ADH97_3-0" class="reference"><a href="#cite_note-ADH97-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> und damit auch in <a href="PSPACE" title="PSPACE">PSPACE</a> enthalten. Es ist unbekannt, ob diese <a href="Teilmenge" title="Teilmenge">Inklusionen</a> echt sind oder nicht.
</p><p>Vazirani und Bernstein zeigten 1997, dass in Berechenbarkeitsmodellen mit <a href="Orakel-Turingmaschine" title="Orakel-Turingmaschine">Orakeln</a> BQP keine Teilmenge von BPP ist, und <a href="Ran_Raz" title="Ran Raz">Ran Raz</a> und Avishay Tal 2018, dass BQP Orakel-separiert von <a href="PH_(Komplexit%C3%A4tsklasse)" class="mw-redirect" title="PH (Komplexitätsklasse)">PH</a> ist.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup>
</p>
<div class="mw-heading mw-heading2"><h2 id="Probleme_in_BQP">Probleme in BQP</h2></div>
<p>Es sind mehrere Probleme in BQP bekannt, von denen vermutet wird, dass sie nicht in BPP liegen. Das bekannteste ist das <a href="Faktorisierung" title="Faktorisierung">Faktorisierungsproblem</a>, das mit dem <a href="Shor-Algorithmus" title="Shor-Algorithmus">Algorithmus von Shor</a> gelöst werden kann.
</p>
<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>
<ol class="references">
<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">Michael Nielsen and Isaac Chuang (2000). <i>Quantum Computation and Quantum Information</i>. Cambridge: Cambridge University Press. ISBN 0-521-63503-9.</span>
</li>
<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text">Bernstein, Vazirani, Quantum complexity theory, SIAM J. Comput., Band 26, Heft 5, 1997, S. 1411–1473, <a rel="nofollow" class="external text" href="https://people.eecs.berkeley.edu/~vazirani/">Online auf der Homepage von Varzirani</a>. Eine vorläufige Zusammenfassung erschien im 25. Annual ACM Symp. Theory Comput. (STOC) 1993, S. 11–20.</span>
</li>
<li id="cite_note-ADH97-3"><span class="mw-cite-backlink"><a href="#cite_ref-ADH97_3-0">↑</a></span> <span class="reference-text">Leonard M. Adleman, Jonathan DeMarrais, Ming-Deh A. Huang: <cite style="font-style:italic">Quantum Computability</cite>. In: <cite style="font-style:italic">SIAM Journal on Computing</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>26</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>5</span>. <a href="SIAM" class="mw-redirect" title="SIAM">SIAM</a>, 1997, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>1524–1540</span> (<a rel="nofollow" class="external text" href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.205.8140&rep=rep1&type=pdf">psu.edu</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:BQP&rft.atitle=Quantum+Computability&rft.au=Leonard+M.+Adleman%2C+Jonathan+DeMarrais%2C+Ming-Deh+A.+Huang&rft.date=1997&rft.genre=journal&rft.issue=5&rft.jtitle=SIAM+Journal+on+Computing&rft.pages=1524-1540&rft.pub=SIAM&rft.volume=26" style="display:none"> </span></span>
</li>
<li id="cite_note-4"><span class="mw-cite-backlink"><a href="#cite_ref-4">↑</a></span> <span class="reference-text"><a rel="nofollow" class="external text" href="https://eccc.weizmann.ac.il/report/2018/107/">Raz, Tal, Oracle Separation of BQP and PH</a>, Electronic Colloquium on Computational Complexity, 2018</span>
</li>
</ol>
<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>
<ul><li><a href="Leonard_Adleman" title="Leonard Adleman">L. Adleman</a>, J. Demarrais, M.A. Huang. <i>Quantum computability</i>. SIAM J. Comp., 26(5): 1524–1540, 1997.</li>
<li>E. Bernstein, U. Vazirani. <i>Quantum complexity theory</i>. SIAM J. Comp., 26(5): 1411–1473, 1997.</li></ul>
<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>
<ul><li><i><a rel="nofollow" class="external text" href="https://complexityzoo.net/Complexity_Zoo:B#bqp">BQP</a>.</i> In: <i>Complexity Zoo.</i> (englisch)</li></ul></div><!--htdig_noindex--><div><div class="zim-footer">
Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2023-05-25" href="https://de.wikipedia.org/wiki/?title=BQP&oldid=234009927">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
<script src="./_webp_/webpHandler.js"></script>
</body></html>